// // DFS(graph, node, target, dist, visited, minDist)
// //     // graph: 图的邻接矩阵表示
// //     // node: 当前正在访问的节点
// //     // target: 目标节点
// //     // dist: 当前路径的累积距离
// //     // visited: 一个布尔数组，标记每个节点是否已被访问
// //     // minDist: 记录从起始节点到目标节点的最小距离

// //     // 如果当前节点是目标节点，则比较并更新最小距离
// //     if node == target then
// //         minDist = min(minDist, dist)
// //         return
// //     end if

// //     // 标记当前节点为已访问
// //     visited[node] = true

// //     // 遍历图中所有可能的邻接节点
// //     for i from 0 to V-1 do
// //         // 如果存在从当前节点到节点i的边，并且节点i未被访问
// //         if graph[node][i] != INF and not visited[i] then
// //             // 递归调用DFS，探索从节点i到目标节点的可能路径
// //             DFS(graph, i, target, dist + graph[node][i], visited, minDist)
// //         end if
// //     end for

// //     // 回溯时，标记当前节点为未访问，以备后续路径探索
// //     visited[node] = false
// // end function

// #include <climits>
// #include <vector>
// #include <iostream>

// const int V = 12;
// const int INF = INT_MAX;
// int minDist = INF;
// std::vector<bool> visited(V, false);

// int graph[V][V] = {
//     {0, 9, 7, 3, 2, INF, INF, INF, INF, INF, INF, INF},
//     {INF, 0, INF, INF, INF, 4, 2, 1, INF, INF, INF, INF},
//     {INF, INF, 0, INF, INF, 2, 7, INF, INF, INF, INF, INF},
//     {INF, INF, INF, 0, INF, INF, INF, 11, INF, INF, INF, INF},
//     {INF, INF, INF, INF, 0, INF, 11, 8, INF, INF, INF, INF},
//     {INF, INF, INF, INF, INF, 0, INF, INF, 6, 5, INF, INF},
//     {INF, INF, INF, INF, INF, INF, 0, INF, 4, 3, INF, INF},
//     {INF, INF, INF, INF, INF, INF, INF, 0, INF, 5, 6, INF},
//     {INF, INF, INF, INF, INF, INF, INF, INF, 0, INF, INF, 4},
//     {INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, INF, 2},
//     {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, INF},
//     {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0}
// };

// void dfs(int node, int target, int dist) {
//     if (node == target) {
//         minDist = std::min(minDist, dist);
//         return;
//     }
//     visited[node] = true;
//     for (int i = 0; i < V; ++i) {
//         if (graph[node][i] != INF && !visited[i]) {
//             dfs(i, target, dist + graph[node][i]);
//         }
//     }
//     visited[node] = false;
// }

// int main() {
//     for (int i = 0; i < V; ++i) {
//         for (int j = 0; j < V; ++j) {
//             if (i != j) {
//                 minDist = INF;
//                 dfs(i, j, 0);
//                 if (minDist == INF) {
//                     std::cout << "No path from " << i << " to " << j << std::endl;
//                 }
//                 else {
//                     std::cout << "Shortest distance from " << i << " to " << j << " is " << minDist << std::endl;
//                 }
//             }
//         }
//     }
//     return 0;
// }


// #include <climits>
// #include <algorithm>
// #include <iostream>

// const int V = 12;
// const int INF = INT_MAX;

// int graph[V][V] = {
//     {0, 9, 7, 3, 2, INF, INF, INF, INF, INF, INF, INF},
//     {INF, 0, INF, INF, INF, 4, 2, 1, INF, INF, INF, INF},
//     {INF, INF, 0, INF, INF, 2, 7, INF, INF, INF, INF, INF},
//     {INF, INF, INF, 0, INF, INF, INF, 11, INF, INF, INF, INF},
//     {INF, INF, INF, INF, 0, INF, 11, 8, INF, INF, INF, INF},
//     {INF, INF, INF, INF, INF, 0, INF, INF, 6, 5, INF, INF},
//     {INF, INF, INF, INF, INF, INF, 0, INF, 4, 3, INF, INF},
//     {INF, INF, INF, INF, INF, INF, INF, 0, INF, 5, 6, INF},
//     {INF, INF, INF, INF, INF, INF, INF, INF, 0, INF, INF, 4},
//     {INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, INF, 2},
//     {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, INF},
//     {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0}
// };

// void floydWarshall() {
//     int dist[V][V];

//     for (int i = 0; i < V; i++)
//         for (int j = 0; j < V; j++)
//             dist[i][j] = graph[i][j];

//     for (int k = 0; k < V; k++)
//         for (int i = 0; i < V; i++)
//             for (int j = 0; j < V; j++)
//                 if (dist[i][k] != INF && dist[k][j] != INF)
//                     dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);

//     // print the shortest distance matrix
//     for (int i = 0; i < V; i++) {
//         for (int j = 0; j < V; j++) {
//             if (dist[i][j] == INF)
//                 std::cout << "INF ";
//             else
//                 std::cout << dist[i][j] << "   ";
//         }
//         std::cout << std::endl;
//     }
// }

// #include <climits>
// #include <algorithm>
// #include <iostream>
// #include <vector>

// const int INF = 100;

// void floydWarshall(std::vector<std::vector<int>>& graph, int V = 10) {
//     //int dist[V][V];

//     int** dist = new int* [V];
//     for (int i = 0; i < V; i++) {
//         dist[i] = new int [V];
//     }
//     for (int i = 0; i < V; i++)
//         for (int j = 0; j < V; j++)
//             dist[i][j] = graph[i][j];

//     for (int k = 0; k < V; k++)
//         for (int i = 0; i < V; i++)
//             for (int j = 0; j < V; j++)
//                 if (dist[i][k] != INF && dist[k][j] != INF)
//                     dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);

//     // print the shortest distance matrix
//     for (int i = 0; i < V; i++) {
//         for (int j = 0; j < V; j++) {
//             if (dist[i][j] == INF)
//                 std::cout << "INF ";
//             else
//                 std::cout << dist[i][j] << "   ";
//         }
//         std::cout << std::endl;
//     }
// }

// //const int INF = INT_MAX;

// std::vector<std::vector<int>> readGraph(int V) {
//     std::vector<std::vector<int>> graph(V, std::vector<int>(V));

//     std::cout << "Please enter the adjacency matrix. Use " << INF << " for infinity:\n";
//     for (int i = 0; i < V; ++i) {
//         for (int j = 0; j < V; ++j) {
//             std::cin >> graph[i][j];
//         }
//     }
    
//     return graph;
// }

// int main() {
//     int V;
//     std::cout << "Enter the number of vertices: ";
//     std::cin >> V;

//     std::vector<std::vector<int>> graph = readGraph(V);

//     floydWarshall(graph, V);
//     return 0;
// }
#include <climits>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int INF = 100;
int minDist = INF;



void dfs(int node, int target, int dist, std::vector<std::vector<int>>& graph, int V, std::vector<bool>& visited) {
    if (node == target) {
        minDist = std::min(minDist, dist);
        return;
    }
    visited[node] = true;
    for (int i = 0; i < V; ++i) {
        if (graph[node][i] != INF && !visited[i]) {
            dfs(i, target, dist + graph[node][i],graph,V,visited);
        }
    }
    visited[node] = false;
}

std::vector<std::vector<int>> readGraph(int V) {
    std::vector<std::vector<int>> graph(V, std::vector<int>(V));

    std::cout << "Please enter the adjacency matrix. Use " << INF << " for infinity:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            std::cin >> graph[i][j];
        }
    }

    return graph;
}

int main() {
    int V;
    std::cout << "Enter the number of vertices: ";
    std::cin >> V;

    std::vector<std::vector<int>> graph = readGraph(V);
    std::vector<bool> visited(V, false);

    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (i != j) {
                minDist = INF;
                dfs(i, j, 0,graph,V,visited);
                if (minDist == INF) {
                    std::cout << "No path from " << i << " to " << j << std::endl;
                }
                else {
                    std::cout << "Shortest distance from " << i << " to " << j << " is " << minDist << std::endl;
                }
            }
        }
    }

    return 0;
}